/**
* essay on linked-list
 * @Author  Knight-errant
*/
package com.godpaper.util
{
	/**
	 * 
	 * Take a look at this example here. Here is a linked list:
     *  first -> 2 -> 5 -> 8 -> 9 -> NULL
	 * Let us say we wish to insert the value 3. 
	 * If the list is unordered, 
	 *  then the value would be inserted at the beginning, 
	 *  and the list would now look as 
	 *  such (note that the value of first would be changed):
     *  first -> 3 -> 2 -> 5 -> 8 -> 9 -> NULL
     * (Note: the altered links and the inserted value are highlighted in red.)
     * If the list were to be ordered, however, 
     *  then the new value would be inserted in the middle of the list:
     *  first -> 2 -> 3 -> 5 -> 8 -> 9 -> NULL
     * Try programming the functions as an exercise. 
     * It really isn't as hard as it may seem.
	 * 
	 */	
	public class LinkedList extends Array
	{
		/**
		 * 
		 * When the list is first initialized, 
		 *  the value of first would be NULL, 
		 *  because the list is empty (i.e. there are no nodes).
		 * When the list is not empty,
		 *  the last node would have their next link point to NULL.
		 * 
		 */		
		public function LinkedList(source:Object=null)
		{
			super();
		}
		
		private var first:LinkedNode; // Pointer to first node
		
		public function print(item:Array):void
		{
			item.toString(); // Prints Entire List
		}
		/**
		 * 
		 * The insert() function depends on whether the linked list
		 * is ordered or not. 
		 * If the linked list is not order, 
		 *  insert() just puts the new value at the beginning of the list.
		 * If the list is ordered, however, 
		 *  then insert() must first find the location for the new node,
		 *  and then insert the node in that location.
		 * 
		 */		
		public function insert(item:Object,ordered:Boolean=false):void
		{
			if(!ordered)
			{
				push(item);
			}else
			{
				insert(item,Boolean(indexOf(item,0)));
			}
		}
		/**
		 * 
		 * The remove() function just goes through the linked list
		 *  and looks for the value given in item. 
		 * If it finds this value, the function removes
		 *  the node containing it and then stops.
		 * 
		 */		
		public function remove(item:Object):void
		{
			if(this.indexOf(item))
			{
				this.splice(this.lastIndexOf(item,0),1);
			}else
			{
				throw(new Error("Can not found your desired item!"));
			}
		}
		/**
		 * 
		 * The search() function just searches the list to see
		 *  if the value in item exists in the list. 
		 * The function returns true if the value was found,
		 *  and false otherwise. 
		 * 
		 */		
		public function search(item:Object):Boolean
		{
			return Boolean(indexOf(item));
		}
		
	}
}
class LinkedNode{
	public var data:int;// Data held by this node
	public var pNext:LinkedNode; // Pointer to next node
}